BOJ16238 독수리

풀이

k마리의 양을 먹을때 이득은 어떻게 구할 수 있을까요? 일단 A를 정렬해서 제일 비싼순서대로 양 k마리(이하 내림차순 k마리)를 먹을 수 있다고 가정하면 (해당 양들 가치의 합 - (0+1+...+k-1)) 입니다. 그리고 k마리의 양을 먹을때 (0+1+...+k-1)는 고정이므로 내림차순 k마리를 먹는게 최선인건 당연하고, 그냥 제일 왼쪽에 있는 애부터 먹으면 항상 내림차순 k마리를 먹을 수 있다는 것을 알 수 있습니다. 이제 몇마리의 양을 먹을 것인지(=k값)를 결정해야 하는데, 이는 제일 비싼 양부터 하나씩 먹으면서 매번 먹을때마다 다음 양의 가치가 1만큼 감소하는 시뮬레이션을 하고, 가치가 음수가 아닐 동안은 다 먹어주는게 최선입니다. 이는 내림차순으로 정렬해서 a[i]-i가 음수가 아닐때까지 계속 선택해주는것과 같습니다.